package lsl.leetCode.test1215;

/**
 * 力扣
 * 70.爬楼梯
 * description:
 *
 * @author: liushengli
 * data: 2022/12/15
 */
public class tset70 {
    public static void main(String[] args) {
        System.out.println(climbStairs(5));
    }


    //动态规划
    public static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] f = new int[n + 1];
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }


    //自顶向下的备忘录法---使用了递归
    public static int Fibonacci(int n) {
        if (n <= 0)
            return n;
        int[] Memo = new int[n + 1];
        for (int i = 0; i <= n; i++)
            Memo[i] = -1;
        return fib(n, Memo);
    }

    public static int fib(int n, int[] Memo) {
        if (Memo[n] != -1)
            return Memo[n];
        //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。
        if (n <= 2)
            Memo[n] = 1;
        else Memo[n] = fib(n - 1, Memo) + fib(n - 2, Memo);
        return Memo[n];
    }
}
